# from typing import List, Dict

# import math

# def combination_num(li):
#     di = {}
#     for index, num in enumerate(li):
#         if num in di.keys():
#             di[num]+=1
#         else:
#             di[num]=1
#     re = math.factorial(len(li))
#     for value in di.values():
#         re /= math.factorial(value)
#     return int(re)

# class Solution:
#     def __init__(self, n=1000):
#         self.methods = [None for _ in range(n+1)]
#         self.methods[2] = 3
#         # 每一阶的分块方法
#         self.divide_methods: List[Dict] = [{} for _ in range(n+1)]
#         # 每一阶的不同分块数量的铺砖方法数
#         self.methods_by_numofblock = [{} for _ in range(n+1)]
#         self.methods_by_numofblock[2][1] = 3

#     # 打印分块方法
#     def log_divide_methods(self):
#         for index, divide_method in enumerate(self.divide_methods):
#             print(f"index: {index}, divide_method: ")
#             for key, value in divide_method.items():
#                 print(f"key: {key}, value: {value}")

#     # 获得固定分块下的组合
#     """
#         24/4 -> 16/1 16/2 16/3 16/4
#     """
#     def get_divide_methods(self, bricknum, blocknum) -> List[List[int]]:
#         if blocknum in self.divide_methods[bricknum].keys():
#             return self.divide_methods[bricknum][blocknum]
#         if bricknum/blocknum == 2:
#             self.divide_methods[bricknum][blocknum] = [[2 for _ in range(blocknum)]]
#             return self.divide_methods[bricknum][blocknum]
#         if blocknum == 1:
#             self.divide_methods[bricknum][blocknum] = [[bricknum]]
#             return self.divide_methods[bricknum][blocknum]
        
#         sub_brick_num = bricknum-blocknum*2
#         if sub_brick_num < 0:
#             self.divide_methods[bricknum][blocknum] = []
#             return []
#         base_list = [2 for _ in range(blocknum)]
#         re = []
#         for i in range(1, blocknum+1):
#             sublists = self.get_divide_methods(sub_brick_num, i)
#             for sublist in sublists:
#                 newlist = [sublist[j]+base_list[j] for j in range(len(sublist))]+base_list[len(sublist):]
#                 re.append(newlist)
#         self.divide_methods[bricknum][blocknum] = re
#         return re


#     # 获得固定分块下的方法数
#     def get_methods_by_numofblock(self, bricknum, blocknum):
#         if blocknum in self.methods_by_numofblock[bricknum].keys():
#             return self.methods_by_numofblock[bricknum][blocknum]
#         if blocknum == 1:
#             return 3 if bricknum == 2 else 2
#         lists = self.get_divide_methods(bricknum, blocknum)
#         re = 0
#         for li in lists:
#             c_num = combination_num(li)
#             method_num=1
#             for num in li:
#                 method_num *= self.get_methods_by_numofblock(num, 1)
#             # print(f"li{li},c_num: {c_num}, method_num: {method_num}, blocked_method_num:{c_num*method_num}")
#             re += c_num*method_num
#         self.methods_by_numofblock[bricknum][blocknum] = re
#         return re




# # def get_methods(n):
# #     array = [0 for _ in range(0,n+1)]
# #     array[2] = 3
# #     if 

# if __name__ == '__main__':
    
#     # a = {}
#     # a[3]=5
#     # print(a)
#     s = Solution()
#     # print(s.get_divide_methods(24, 4))
#     n = int(input())
#     methods = 0
#     for i in range(1,n//2+1):
#         print(f"i: {i}")
#         methods += s.get_methods_by_numofblock(n, i)
#     print(methods)

def count_tiling_ways(n):
    if n % 2 != 0:
        return 0  # 如果 n 是奇数，无法铺满
    
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[2] = 3
    
    for i in range(4, n + 1, 2):
        dp[i] = 4 * dp[i-2] - dp[i-4]
    
    return dp[n]

if __name__ == '__main__':
    outlist = []
    while True:
        n = int(input())
        if n == 0:
            break
        outlist.append(count_tiling_ways(n)%100003)
    for i in outlist:
        print(i)